
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

/**
 * @ClassName BinaryTree
 * @Description TODO
 * @Author ZJX
 * @Date 2024/7/23 22:49
 * @Version 1.0
 */
public  class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //    穷举方式创建二叉树
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
/*
        A
       / \
      B   C
     / \ / \
    D  E F  G
         \
          H
*/
    }

    // 前序遍历
    void preOrder(TreeNode root) {
//        空树直接返回
        if (root == null) {
            return;
        }
        System.out.print(root.val + " "); // 打印根节点
        preOrder(root.left); // 遍历左子树
        preOrder(root.right); // 遍历右子树
    }

    // 中序遍历
    void inOrder(TreeNode root) {
//        中序遍历 : 左 根 右
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    // 后序遍历
    void postOrder(TreeNode root) {
//        后序遍历: 左 右 根
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }


    // 获取树中节点的个数
    int size(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + size(root.left) + size(root.right); // 左树节点加上右树节点再加上跟节点
    }

    public int num;

    // 获取叶子节点的个数   遍历思路: 遍历二叉树 使用计数器存储叶子结点的个数
    int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            num++;
        } else {
            getLeafNodeCount(root.left);
            getLeafNodeCount(root.right);
        }
        return num;
    }

    // 子问题思路-求叶子结点个数    整个树的叶子 = 左子树叶子 + 右子树叶子数
    int getLeafNodeCount1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);

    }

    // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }

    // 获取二叉树的高度
    int getHeight(TreeNode root) {
//        二叉树的高度 = 左右子树高度的较大值 + 1(根节点)
        if (root == null) {
            return 0;
        }

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? (leftHeight + 1) : (rightHeight + 1);
    }

    // 检测值为value的元素是否存在
    Boolean find(TreeNode root, int val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        return find(root.left, val) || find(root.right, val);
    }

    /*
     * @param p:
     * @param q:
     * @return boolean
     * @author: ZJX
     * @description: 力扣 100 相同的树
     * @date: 2024/7/24 19:29
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 如果两个节点都是空，返回true
        if (p == null && q == null) {
            return true;
        }
        // 如果其中一个节点为空，另一个不为空，返回false
        if (p == null || q == null) {
            return false;
        }
        // 如果两个节点的值不相同，返回false
        if (p.val != q.val) {
            return false;
        }
        // 递归比较左子树和右子树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    /*
     * @param root:
     * @param subRoot:
     * @return boolean
     * @author: ZJX
     * @description: 力扣 572 另一棵树的子树
     * @date: 2024/7/24 20:01
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
//            判断空树
            return subRoot == null;
        }
        if (isSameTree(root, subRoot)) {
//            判断是否相同
            return true;
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    /*
     * @param root:
     * @return BinaryTree.TreeNode
     * @author: ZJX
     * @description: 翻转二叉树
     * @date: 2024/7/24 20:52
     */
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode leftNode = mirrorTree(root.left);
        TreeNode rightNode = mirrorTree(root.right);

        // 交换左右子树
        root.left = rightNode;
        root.right = leftNode;

        return root;
    }

    /*
     * @param root:
     * @return boolean
     * @author: ZJX
     * @description: 力扣 110 平衡二叉树
     *      平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1
     * @date: 2024/7/24 21:23
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
//        思路: 计算出 左右子树的高度 看是否满足平衡二叉树的条件
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    /*
     * @param root:
     * @return boolean
     * @author: ZJX
     * @description: 判断对称二叉树 LCR145
     * @date: 2024/7/25 8:33
     */
    public boolean checkSymmetricTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null || right == null) {
            return left == right;
        }
        return (left.val == right.val) && isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }

    //层序遍历
    void levelOrder(TreeNode root) {
//        使用队列来实现 从上到下 从左到右
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");

            if (cur.left != null) {
                queue.offer(cur.left);
            }

            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    /*
     * @param root:
     * @return java.util.List<java.util.List<java.lang.Integer>>
     * @author: ZJX
     * @description: 力扣 102 二叉树的层序遍历  二维数组用于接收一维数组
     * @date: 2024/7/26 6:44
     */
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Integer> temp = new LinkedList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                temp.add((int) node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(temp);
        }
        return ret;
    }

    // 判断一棵树是不是完全二叉树 使用层序遍历解决
//    遇到第一个空节点之后 其余的都是空才是完全二叉树
    boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean findNull = false;

        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur == null) {
                findNull = true;
            } else {
                if (findNull) {
                    return false; //遇到第一个空节点之后还有空节点 说明不是完全二叉树
                }
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
        }
        return true;
    }


    /*
     * @param root:
     * @return java.util.List<java.lang.Integer>
     * @author: ZJX
     * @description: 输出二叉树的左视图 阿里面试题
     * @date: 2024/7/26 8:49
     */
    public List<Integer> leftSideView(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (i == 0) {
                    ret.add((int) cur.val); // 直接添加当前层的第一个节点的值
                }
                // 添加子节点到队列，只添加非空的子节点
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        return ret;
    }

    /*
     * @param root:
     * @param p:
     * @param q:
     * @return BinaryTree.TreeNode
     * @author: ZJX
     * @description: 最近公共祖先问题 力扣236
     * @date: 2024/7/26 13:16
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        return null;
    }

    /*
     * @param preorder:
     * @param inorder:
     * @return BinaryTree.TreeNode
     * @author: ZJX
     * @description: 力扣 105 根据前序遍历与中序遍历 构建二叉树
     * @date: 2024/7/27 20:50
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder, inorder, 0, 0, inorder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
        if (preStart > preorder.length - 1 || inStart >= inEnd) {
            return null; // 递归终止条件
        }

        // 当前根节点
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode((char) rootVal);

        // 找到根节点在中序遍历中的位置
        int index = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }

        // 递归构建左右子树
        root.left = buildTreeHelper(preorder, inorder, preStart + 1, inStart, index - 1);
        root.right = buildTreeHelper(preorder, inorder, preStart + 1 + (index - inStart), index + 1, inEnd);

        return root;
    }

    /*
     * @param inorder:
     * @param postorder:
     * @return BinaryTree.TreeNode
     * @author: ZJX
     * @description: 利用中序后序遍历创建二叉树 力扣106
     * @date: 2024/7/28 10:41
     */
    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        return buildTreeHelper1(inorder, postorder, 0, postorder.length - 1, postorder.length - 1);
    }

    private TreeNode buildTreeHelper1(int[] inorder, int[] postorder, int inStart, int inEnd, int postIndex) {
//        递归终止条件
        if (inStart > inEnd) {
            return null;
        }

//        创建根节点
        int rootVal = postorder[postIndex];
        TreeNode root = new TreeNode((char) rootVal);

//        在中序遍历中找根节点
        int inorderIndex = findInorderIndex(inorder, rootVal, inStart, inEnd);

        root.right = buildTreeHelper1(inorder, postorder, inorderIndex + 1, inEnd, postIndex - 1);
        root.left = buildTreeHelper1(inorder, postorder, inStart, inorderIndex - 1, postIndex - (inEnd - inorderIndex) - 1);

        return root;
    }

    private int findInorderIndex(int[] inorder, int rootVal, int start, int end) {
        for (int i = start; i < end; i++) {
            if (inorder[i] == rootVal) {
                return i;
            }
        }
        return -1;
    }

    /*
     * @param root:
     * @return java.lang.String
     * @author: ZJX
     * @description: 力扣 606
     * @date: 2024/7/28 14:30
     */
    public static String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strHelper(root, stringBuilder);
        return stringBuilder.toString();
    }

    private static void tree2strHelper(TreeNode root, StringBuilder stringBuilder) {
        if (root == null) {
            return;
        }
        stringBuilder.append(root.val);

        // 处理左子树和右子树
        if (root.left != null || root.right != null) {
            // 左子树存在，或者右子树存在
            stringBuilder.append("("); // 添加左子树的左括号
            tree2strHelper(root.left, stringBuilder); // 递归处理左子树
            stringBuilder.append(")"); // 添加左子树的右括号

            if (root.right != null) {
                // 右子树存在
                stringBuilder.append("("); // 添加右子树的左括号
                tree2strHelper(root.right, stringBuilder); // 递归处理右子树
                stringBuilder.append(")"); // 添加右子树的右括号
            }
        }
    }

    /*
     * @param root:
      * @return java.util.List<java.lang.Integer>
     * @author: ZJX
     * @description:  Iterative 迭代  二叉树前序遍历的迭代法
     * @date: 2024/7/28 17:46
     */
    public List<Integer> preorderTraversalIterative(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null){
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            result.add((int) cur.val);

//            栈是后进先出的结构
            if (cur.right != null){
                stack.push(cur.right);
            }
            if (cur.left != null){
                stack.push(cur.left);
            }
        }
        return result;
    }

    /*
     * @param root:
      * @return java.util.List<java.lang.Integer>
     * @author: ZJX
     * @description:  二叉树中序遍历  迭代法
     * @date: 2024/7/28 18:34
     */
    public List<Integer> inorderTraversalIterative(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            result.add((int) cur.val);
            cur = cur.right;
        }
        return result;
    }

    /*
     * @param root:
      * @return java.util.List<java.lang.Integer>
     * @author: ZJX
     * @description: 二叉树后序遍历 迭代法
     * @date: 2024/7/28 18:35
     */
    public List<Integer> postorderTraversalIterative(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode prev = null; // 上一个访问的节点

        while (!stack.isEmpty()) {
            TreeNode cur = stack.peek();

            // 如果当前节点是叶子节点或者上一个访问的节点是当前节点的子节点
            if (cur.left == null && cur.right == null ||
                    prev != null && (prev == cur.left || prev == cur.right)) {
                result.add((int) cur.val);
                stack.pop();
                prev = cur;
            } else {
                // 否则，按后序遍历的顺序将子节点压栈
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
        return result;
    }

    /*
     * @param root:
      * @return java.util.List<java.lang.Integer>
     * @author: ZJX
     * @description: 后序遍历非递归实现（优化版） 使用两个栈
     * @date: 2024/7/29 7:34
     */
    public List<Integer> postorderTraversalIterative1(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>(); // 模拟遍历
        Stack<TreeNode> output = new Stack<>(); // 存储后序遍历的结果
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            output.push(node);

            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        while (!output.isEmpty()) {
            result.add((int) output.pop().val);
        }

        return result;
    }

    public static TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode temp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(temp);

        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode('A');
        root.left = new TreeNode('B');
        root.right = new TreeNode('C');
        root.left.left = new TreeNode('D');
        root.right.right = new TreeNode('G');

        TreeNode invertedRoot = invertTree(root);
        System.out.println(tree2str(invertedRoot));
    }
}
